{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Array of Doubled Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canReorderDoubled"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二倍数对数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为偶数的整数数组 <code>arr</code>，只有对 <code>arr</code> 进行重组后可以满足 “对于每个 <code>0 &lt;=&nbsp;i &lt; len(arr) / 2</code>，都有 <code>arr[2 * i + 1] = 2 * arr[2 * i]</code>”&nbsp;时，返回 <code>true</code>；否则，返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [3,1,3,6]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [2,1,2,6]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [4,-2,2,-4]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= arr.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>arr.length</code> 是偶数</li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= arr[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [array-of-doubled-pairs](https://leetcode.cn/problems/array-of-doubled-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [array-of-doubled-pairs](https://leetcode.cn/problems/array-of-doubled-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,3,6]', '[2,1,2,6]', '[4,-2,2,-4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        \n",
    "        numSet = set(arr)\n",
    "        numList = list(numSet)\n",
    "        numList.sort()\n",
    "        nSet = len(numSet)\n",
    "        \n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            if arr[i] not in dic:\n",
    "                dic[arr[i]] = 1\n",
    "            else:\n",
    "                dic[arr[i]] += 1\n",
    "        \n",
    "        for num in numList[::-1]:\n",
    "            if dic[num] == 0:\n",
    "                continue\n",
    "            half = num/2 if num>0 else num*2\n",
    "            if half not in dic or dic[num] > dic[half]:\n",
    "                return False\n",
    "            else:\n",
    "                \n",
    "                dic[half] -= dic[num]\n",
    "                dic[num] = 0\n",
    "        \n",
    "        if len(set(dic.values())) != 1:\n",
    "            return False\n",
    "        if 0 not in dic.values():\n",
    "            return False\n",
    "        return True\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        arr.sort()\n",
    "        canUse=set()\n",
    "        print(arr)\n",
    "        index=len(arr)-1\n",
    "        oldindex2=index\n",
    "        while arr:\n",
    "            i=arr.pop()\n",
    "            if index in canUse:\n",
    "                index-=1\n",
    "                oldindex2=index\n",
    "                continue\n",
    "            index -= 1\n",
    "            if i>=0:\n",
    "                i2=i/2\n",
    "                index2=bisect_right(arr,i2,0,oldindex2)-1\n",
    "            else:\n",
    "                i2=i*2\n",
    "                index2=bisect_right(arr,i2,0,oldindex2)-1\n",
    "            print(i,i2,index,index2)\n",
    "            if index2<oldindex2 and arr[index2]==i2:\n",
    "                oldindex2=index2\n",
    "                canUse.add(index2)\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "        \n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            if arr[i] not in dic:\n",
    "                dic[arr[i]] = 1\n",
    "            else:\n",
    "                dic[arr[i]] += 1\n",
    "        \n",
    "        # for num in sorted(dic, key = abs):\n",
    "        #     if dic[num] == 0:\n",
    "        #         continue\n",
    "        #     doub = 2*num\n",
    "        #     if doub not in dic or dic[doub] < dic[num]:\n",
    "        #         return False\n",
    "        #     dic[doub] -= dic[num]\n",
    "        # return True\n",
    "        \n",
    "        numSet = set(arr)\n",
    "        numList = list(numSet)\n",
    "        numList.sort()\n",
    "        nSet = len(numSet)\n",
    "        \n",
    "        for num in numList[::-1]:\n",
    "            if dic[num] == 0:\n",
    "                continue\n",
    "            half = num/2 if num>0 else num*2\n",
    "            if half not in dic or dic[num] > dic[half]:\n",
    "                return False\n",
    "            else:              \n",
    "                dic[half] -= dic[num]\n",
    "                dic[num] = 0\n",
    "        \n",
    "        # if len(set(dic.values())) != 1:\n",
    "        #     return False\n",
    "        # if 0 not in dic.values():\n",
    "        #     return False\n",
    "        return True\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        counter = collections.Counter(arr)\n",
    "\n",
    "        def cmp(a, b):\n",
    "            if a >= 0 and b >= 0:\n",
    "                return a - b\n",
    "            if a < 0 and b < 0:\n",
    "                return b - a\n",
    "            if a >= 0:\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        arr = sorted(arr, key=functools.cmp_to_key(cmp))\n",
    "        used = collections.Counter()\n",
    "        for num in arr:\n",
    "            if used[num] > 0:\n",
    "                used[num] -= 1\n",
    "                continue\n",
    "            if (t := num << 1) not in counter:\n",
    "                return False\n",
    "            used[t] += 1\n",
    "            counter[t] -= 1\n",
    "            if counter[t] == 0:\n",
    "                counter.pop(t)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        st = defaultdict(int)\n",
    "        for num in arr:\n",
    "            st[num] += 1\n",
    "\n",
    "        arr.sort()\n",
    "        for num in arr:\n",
    "            if st[num] == 0:\n",
    "                continue\n",
    "            tmp = 2 * num if num >= 0 else num / 2\n",
    "            if st[tmp] > 0:\n",
    "                st[num] -= 1\n",
    "                st[tmp] -= 1\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for x in sorted(cnt, key=abs):\n",
    "            if cnt[2 * x] < cnt[x]:\n",
    "                return False\n",
    "            cnt[2 * x] -= cnt[x]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "\n",
    "        pos = []# collections.deque()\n",
    "        neg = []#collections.deque()\n",
    "\n",
    "\n",
    "        for num in arr:\n",
    "            if num >= 0:\n",
    "                pos.append(num)\n",
    "            else:\n",
    "                neg.append(num)\n",
    "        \n",
    "        pos.sort()\n",
    "        neg.sort(reverse=True)\n",
    "\n",
    "        idx1 = 0\n",
    "        set1 = set()\n",
    "        q1 = collections.deque()\n",
    "        for i,num in enumerate(pos):\n",
    "            if q1 and num / 2 == q1[0][1]:\n",
    "                idx,n1 = q1.popleft()\n",
    "                # set1.add(idx)\n",
    "                # set1.add(i)\n",
    "            else:\n",
    "                q1.append( (i,num) )\n",
    "        \n",
    "        if q1:\n",
    "            return False\n",
    "        \n",
    "        for i, num in enumerate(neg):\n",
    "            if q1 and num / 2 == q1[0][1]:\n",
    "                idx,n1 = q1.popleft()\n",
    "                # set1.add(idx)\n",
    "                # set1.add(i)\n",
    "            else:\n",
    "                q1.append((i,num))\n",
    "\n",
    "        return False if q1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for x in sorted(cnt):\n",
    "            if x > 0:\n",
    "                if cnt[2 * x] < cnt[x]:\n",
    "                    return False\n",
    "                else:\n",
    "                    cnt[2 * x] -= cnt[x]\n",
    "            if x < 0:\n",
    "                if cnt[x / 2] < cnt[x]:\n",
    "                    return False\n",
    "                else:\n",
    "                    cnt[x / 2] -= cnt[x]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "        vis = [False] * n\n",
    "        arr.sort()\n",
    "        d = defaultdict(list)\n",
    "        for i, v in enumerate(arr):\n",
    "            d[v].append(i)\n",
    "        if len(d[0]) % 2 != 0:\n",
    "            return False\n",
    "\n",
    "        for i, v in enumerate(arr):\n",
    "            if vis[i] or v == 0: continue\n",
    "            if v < 0 and v % 2 != 0: continue\n",
    "            t = v // 2 if v < 0 else v * 2\n",
    "            if not d[t]:\n",
    "                return False\n",
    "            vis[d[t].pop()] = True\n",
    "            vis[i] = True\n",
    "\n",
    "        return all(v for i, v in enumerate(vis) if arr[i])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        num_map = collections.Counter(arr)\n",
    "        for num in sorted(num_map, key=abs):\n",
    "            if num_map[num] > num_map[2 * num]:\n",
    "                return False\n",
    "            num_map[2 * num] -= num_map[num]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnts = Counter(arr)\n",
    "        for k in sorted(cnts.keys()):\n",
    "            # 正数和自己乘二配对\n",
    "            if k > 0 and cnts[k * 2] < cnts[k]:\n",
    "                return False\n",
    "            elif k > 0:\n",
    "                cnts[k * 2] -= cnts[k]\n",
    "            # 负数要和自己除二配对，因为是除法要讨论奇偶\n",
    "            elif k < 0 and cnts[k] and (k % 2 or cnts[k // 2] < cnts[k]):\n",
    "                return False\n",
    "            elif k < 0:\n",
    "                cnts[k / 2] -= cnts[k]\n",
    "            # 0本身要自己有偶数个，才能配对\n",
    "            elif cnts[k] % 2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        arr.sort()\n",
    "        c = Counter()\n",
    "        for x in arr:\n",
    "            if x >= 0:\n",
    "                if x & 1:\n",
    "                    c[x] += 1\n",
    "                elif (y := x >> 1) in c:\n",
    "                    c[y] -= 1\n",
    "                    if c[y] == 0:\n",
    "                        del c[y]\n",
    "                else:\n",
    "                    c[x] += 1\n",
    "            else:\n",
    "                if (y := x << 1) in c:\n",
    "                    c[y] -= 1\n",
    "                    if c[y] == 0:\n",
    "                        del c[y]\n",
    "                elif x & 1:\n",
    "                    return False\n",
    "                else:\n",
    "                    c[x] += 1\n",
    "        return not c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "        \n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            if arr[i] not in dic:\n",
    "                dic[arr[i]] = 1\n",
    "            else:\n",
    "                dic[arr[i]] += 1\n",
    "        \n",
    "        \n",
    "        numSet = set(arr)\n",
    "        numList = list(numSet)\n",
    "        numList.sort()\n",
    "        nSet = len(numSet)\n",
    "        \n",
    "        for num in numList[::-1]:\n",
    "            if dic[num] == 0:\n",
    "                continue\n",
    "            half = num/2 if num>0 else num*2\n",
    "            if half not in dic or dic[num] > dic[half]:\n",
    "                return False\n",
    "            else:              \n",
    "                dic[half] -= dic[num]\n",
    "                dic[num] = 0\n",
    "        \n",
    "        if len(set(dic.values())) != 1:\n",
    "            return False\n",
    "        if 0 not in dic.values():\n",
    "            return False\n",
    "        return True\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "        for x in sorted(cnt, key=abs):\n",
    "            if cnt[x] > cnt[2 * x]:\n",
    "                return False\n",
    "            cnt[2 * x] -= cnt[x]\n",
    "        return True\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = collections.Counter(arr)\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for x in sorted(cnt, key=abs):\n",
    "            if cnt[2 * x] < cnt[x]:\n",
    "                return False\n",
    "            cnt[2 * x] -= cnt[x]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        d = collections.defaultdict(int)\n",
    "        for num in arr:\n",
    "            d[num] += 1\n",
    "        \n",
    "        if d[0] % 2:\n",
    "            return False\n",
    "        \n",
    "        for x in sorted(d, key=abs):\n",
    "            if d[2*x] < d[x]:\n",
    "                return False\n",
    "            d[2*x] -= d[x]\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt=collections.Counter(arr)\n",
    "        if len(arr)%2==1:\n",
    "            return False\n",
    "        for x in sorted(cnt,key=abs):\n",
    "            if cnt[x]>cnt[2*x]:\n",
    "                return False\n",
    "            cnt[2*x]-=cnt[x]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = defaultdict(int)\n",
    "        for x in arr:\n",
    "            cnt[x] += 1\n",
    "        for x in sorted(cnt.keys(), key=abs):\n",
    "            if cnt[x*2] < cnt[x]:\n",
    "                return False\n",
    "            cnt[x*2] -= cnt[x]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "        for x in sorted(cnt, key=abs):\n",
    "            if cnt[2 * x] < cnt[x]:  # 无法找到足够的 2x 与 x 配对\n",
    "                return False\n",
    "            cnt[2 * x] -= cnt[x]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt=Counter(arr)\n",
    "        if cnt[0]%2!=0: return False\n",
    "        for x in sorted(cnt,key=abs):\n",
    "            if cnt[2*x]<cnt[x]:return False\n",
    "            cnt[2*x]-=cnt[x]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt=collections.Counter(arr)\n",
    "        for x in sorted(cnt.keys(),key=lambda x:abs(x)):\n",
    "            y=2*x\n",
    "            if cnt[y]<cnt[x]:\n",
    "                print()\n",
    "                return False\n",
    "            else:\n",
    "                cnt[y]-=cnt[x]\n",
    "                cnt[x]=0\n",
    "        return True\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = collections.Counter(arr)\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for x in sorted(cnt, key=abs):\n",
    "            if cnt[2 * x] < cnt[x]:\n",
    "                return False\n",
    "            cnt[2 * x] -= cnt[x]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        seen = dict()\n",
    "        for v, cnt in sorted(collections.Counter(arr).items(), key=lambda x: abs(x[0])):\n",
    "            if v == 0:\n",
    "                if cnt & 1:\n",
    "                    return False\n",
    "                continue\n",
    "            if not v & 1 and v >> 1 in seen:\n",
    "                if seen[v >> 1] > cnt:\n",
    "                    return False\n",
    "                cnt -= seen[v >> 1]\n",
    "                del seen[v >> 1]\n",
    "            seen[v] = cnt\n",
    "        return all([v == 0 for v in seen.values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\r\n",
    "        cnt = Counter(arr)\r\n",
    "        arr.sort()\r\n",
    "        for num in arr:\r\n",
    "            if cnt[num]<=0:\r\n",
    "                continue\r\n",
    "            if num<0:\r\n",
    "                if num%2==1 or cnt[num//2]<=0:\r\n",
    "                    return False\r\n",
    "                cnt[num//2]-=1\r\n",
    "            else:\r\n",
    "                if cnt[num*2]<=0:\r\n",
    "                    return False\r\n",
    "                cnt[num*2]-=1\r\n",
    "            cnt[num]-=1\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        dic = collections.defaultdict(int)\n",
    "        arr.sort()\n",
    "        for i in arr:\n",
    "            dic[i] += 1\n",
    "\n",
    "        for i in arr:\n",
    "            if dic[i] and dic[i*2]:\n",
    "                dic[i] -= 1\n",
    "                dic[i*2] -= 1\n",
    "\n",
    "        for i in arr:\n",
    "            if dic[i]:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for x in sorted(cnt, key=abs):\n",
    "            if cnt[2 * x] < cnt[x]:  # 无法找到足够的 2x 与 x 配对\n",
    "                return False\n",
    "            cnt[2 * x] -= cnt[x]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        num_map = Counter(arr)\n",
    "        for num in sorted(num_map, key=abs):\n",
    "            if num_map[num] > num_map[2 * num]:\n",
    "                return False\n",
    "            num_map[2 * num] -= num_map[num]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt=Counter(arr)\n",
    "        if cnt[0]%2==1:\n",
    "            return False\n",
    "        for x in sorted(cnt, key=lambda x:abs(x)):\n",
    "            if cnt[2*x]<cnt[x]:\n",
    "                return False\n",
    "            cnt[2*x]-=cnt[x]\n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for x in sorted(cnt, key=abs):\n",
    "            if cnt[2 * x] < cnt[x]:  # 无法找到足够的 2x 与 x 配对\n",
    "                return False\n",
    "            cnt[2 * x] -= cnt[x]\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt=Counter(arr)\n",
    "        if cnt[0]%2!=0:\n",
    "            return False\n",
    "        for i in sorted(cnt,key=abs):\n",
    "            if cnt[2*i]<cnt[i]:\n",
    "                return False\n",
    "            cnt[2*i]-=cnt[i]\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "        #print(cnt)\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for x in sorted(cnt, key=abs):\n",
    "            if cnt[2 * x] < cnt[x]:  # 无法找到足够的 2x 与 x 配对\n",
    "                return False\n",
    "            cnt[2 * x] -= cnt[x]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "\n",
    "        for num in sorted(arr) :\n",
    "            if num * 2 in cnt:\n",
    "                while cnt[num]>0 and cnt[num*2]>0:\n",
    "                    cnt[num] -= 1\n",
    "                    cnt[num*2] -= 1\n",
    "\n",
    "                if not cnt[num]:\n",
    "                    del cnt[num]\n",
    "                if not cnt[num*2]:\n",
    "                    del cnt[num*2]\n",
    "\n",
    "        return not cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnts = Counter(arr)\n",
    "        for num in sorted(cnts.keys(), key=abs):\n",
    "            if num==0:\n",
    "                if cnts[num]%2==1:\n",
    "                    return False\n",
    "            else:\n",
    "                if cnts[num*2]<cnts[num]:\n",
    "                    return False\n",
    "                cnts[2*num]-=cnts[num]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        map = Counter(arr)\n",
    "        if map[0] % 2:\n",
    "            return False\n",
    "        for x in sorted(map, key=abs):\n",
    "            if map[2 * x] < map[x]:\n",
    "                return False\n",
    "            map[2 * x] -= map[x]\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        arr.sort()\n",
    "        c = Counter()\n",
    "        for x in arr:\n",
    "            if (y := x << 1) in c:\n",
    "                c[y] -= 1\n",
    "                if c[y] == 0:\n",
    "                    del c[y]\n",
    "            elif not x & 1 and (y := x >> 1) in c:\n",
    "                c[y] -= 1\n",
    "                if c[y] == 0:\n",
    "                    del c[y]\n",
    "            else:\n",
    "                c[x] += 1\n",
    "        return not c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        from collections import Counter\n",
    "\n",
    "        count = Counter(arr)\n",
    "        for x in sorted(count, key=abs):\n",
    "            if count[2 * x] < count[x]:\n",
    "                return False\n",
    "            count[2 * x] -= count[x]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnts = Counter([v for v in arr])\n",
    "        if 0 in cnts:\n",
    "            if cnts[0]&1 != 0:\n",
    "                return False  \n",
    "        def f(keys: List[int]) -> bool:\n",
    "            n = len(keys)\n",
    "            for i in range(n):\n",
    "                v = keys[i]\n",
    "                if cnts[v] == 0:\n",
    "                    continue\n",
    "                if cnts[v] < 0:\n",
    "                    return False\n",
    "                if 2*v not in cnts:\n",
    "                    return False\n",
    "                cnts[2*v] -= cnts[v]\n",
    "            return True\n",
    "        l = list(cnts.keys())\n",
    "        return f(sorted([v for v in l if v > 0])) and f(sorted([v for v in l if v < 0], reverse=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        arr.sort()\n",
    "        d = deque()\n",
    "        for x in arr:\n",
    "            if not d:\n",
    "                d.append(x)\n",
    "            elif x == d[0] * 2 or x * 2 == d[0]:\n",
    "                d.popleft()\n",
    "            else:\n",
    "                d.append(x)\n",
    "        return len(d) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for x in sorted(cnt, key=abs):\n",
    "            if cnt[2 * x] < cnt[x]:  # 无法找到足够的 2x 与 x 配对\n",
    "                return False\n",
    "            cnt[2 * x] -= cnt[x]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        num_map = collections.Counter(arr)\n",
    "        for num in sorted(num_map, key=abs):\n",
    "            if num_map[num] > num_map[2 * num]:\n",
    "                return False\n",
    "            num_map[2 * num] -= num_map[num]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "        for x in sorted(cnt, key=abs):\n",
    "            if cnt[x << 1] < cnt[x]:  # 无法找到足够的 2x 与 x 配对\n",
    "                return False\n",
    "            cnt[x << 1] -= cnt[x]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "        \n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            if arr[i] not in dic:\n",
    "                dic[arr[i]] = 1\n",
    "            else:\n",
    "                dic[arr[i]] += 1\n",
    "        \n",
    "        # for num in sorted(dic, key = abs):\n",
    "        #     if dic[num] == 0:\n",
    "        #         continue\n",
    "        #     doub = 2*num\n",
    "        #     if doub not in dic or dic[doub] < dic[num]:\n",
    "        #         return False\n",
    "        #     dic[doub] -= dic[num]\n",
    "        # return True\n",
    "        \n",
    "        numSet = set(arr)\n",
    "        numList = list(numSet)\n",
    "        numList.sort()\n",
    "        nSet = len(numSet)\n",
    "        \n",
    "        for num in numList[::-1]:\n",
    "            if dic[num] == 0:\n",
    "                continue\n",
    "            half = num/2 if num>0 else num*2\n",
    "            if half not in dic or dic[num] > dic[half]:\n",
    "                return False\n",
    "            else:              \n",
    "                dic[half] -= dic[num]\n",
    "                dic[num] = 0\n",
    "        \n",
    "        if len(set(dic.values())) != 1:\n",
    "            return False\n",
    "        if 0 not in dic.values():\n",
    "            return False\n",
    "        return True\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        \n",
    "        #arr.sort()\n",
    "\n",
    "        dist = {}\n",
    "\n",
    "        for num in arr:\n",
    "            if num not in dist:\n",
    "                dist[num] = 1\n",
    "            else:\n",
    "                dist[num] += 1\n",
    "\n",
    "        \n",
    "        disted = sorted(dist, key = abs)\n",
    "        print(dist)\n",
    "\n",
    "        if 0 in dist and dist[0] % 2 != 0:\n",
    "            return False\n",
    "\n",
    "        for num in disted:\n",
    "            print(num)\n",
    "            if dist[num] == 0:\n",
    "                continue\n",
    "\n",
    "            if num * 2 in dist:\n",
    "                if dist[num * 2] < dist[num]:    \n",
    "                    return False\n",
    "                #print(dist)\n",
    "                dist[num * 2] -= dist[num]\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        pos = [num for num in arr if num > 0]\n",
    "        neg = [num for num in arr if num < 0]\n",
    "        zero = arr.count(0)\n",
    "        if zero % 2:\n",
    "            return False\n",
    "        \n",
    "        cnt = Counter(pos)\n",
    "        pos.sort()\n",
    "        for num in pos:\n",
    "            if not cnt[num]:\n",
    "                continue\n",
    "     \n",
    "            if cnt[2*num] < 1:\n",
    "                return False\n",
    "            cnt[num] -= 1\n",
    "            cnt[2*num] -= 1\n",
    "\n",
    "        cnt = Counter(neg)\n",
    "        neg.sort(reverse=True)\n",
    "        for num in neg:\n",
    "            if not cnt[num]:\n",
    "                continue\n",
    "            x = 1\n",
    "            cnt[num] -= 1\n",
    "            if cnt[2 * num] < x:\n",
    "                return False\n",
    "            cnt[2 * num] -= x\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = Counter(arr)\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for i in sorted(cnt,key = abs):\n",
    "            if cnt[2*i] < cnt[i]:\n",
    "                return False\n",
    "            else:\n",
    "                cnt[2*i] -= cnt[i]\n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt = collections.Counter(arr)\n",
    "        if cnt[0] % 2:\n",
    "            return False\n",
    "        for i in sorted(cnt, key = abs):\n",
    "            if cnt[i] > cnt[2 * i]:\n",
    "                return False\n",
    "            cnt[2 * i] -= cnt[i]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        arr_a = []\n",
    "        arr_b = []\n",
    "        for item in arr:\n",
    "            if item >= 0:\n",
    "                arr_a.append(item)\n",
    "            else:\n",
    "                arr_b.append(item)\n",
    "        arr_a.sort()\n",
    "        arr_b.sort(reverse=True)\n",
    "        counter = 0\n",
    "        left = {}\n",
    "        over = []\n",
    "        for item in list(set(arr_a)):\n",
    "            double = 2 * item\n",
    "            if item in over:\n",
    "                continue\n",
    "            if item == double:\n",
    "                counter += arr.count(item) // 2\n",
    "                continue\n",
    "            if double in arr:\n",
    "                if item in left:\n",
    "                    a = left[item]\n",
    "                else:\n",
    "                    a = arr.count(item)\n",
    "                b = arr.count(double)\n",
    "                if a >= b:\n",
    "                    counter += b\n",
    "                    over.append(double)\n",
    "                else:\n",
    "                    counter += a\n",
    "                    left[double] = b - a\n",
    "        temp = list(set(arr_b))\n",
    "        temp.sort(reverse=True)\n",
    "        for item in temp:\n",
    "            double = 2 * item\n",
    "            if item in over:\n",
    "                continue\n",
    "            if item == double:\n",
    "                counter += arr.count(item) // 2\n",
    "                continue\n",
    "            if double in arr:\n",
    "                if item in left:\n",
    "                    a = left[item]\n",
    "                else:\n",
    "                    a = arr.count(item)\n",
    "                b = arr.count(double)\n",
    "                if a >= b:\n",
    "                    counter += b\n",
    "                    over.append(double)\n",
    "                else:\n",
    "                    counter += a\n",
    "                    left[double] = b - a\n",
    "        if counter == len(arr) // 2:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "   检测一下，注意正负数即可\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "        arr.sort(key = lambda p: abs(p))\n",
    "        cnt = Counter(arr)\n",
    "        for num in arr:\n",
    "            if cnt[num] == 0: continue\n",
    "            cnt[num] -= 1\n",
    "            if cnt[2*num]:\n",
    "                cnt[2*num] -= 1\n",
    "            else:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        di = dict()\n",
    "        for num in arr:\n",
    "            di[num] = di.get(num, 0) + 1\n",
    "        for num in sorted(di.keys(), key=abs):\n",
    "            if di.get(2 * num, 0) < di.get(num, 0):\n",
    "                return False\n",
    "            if 2 * num in di:\n",
    "                di[2 * num] -= di[num]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        m=len(arr)\n",
    "        ls=[]\n",
    "        c=collections.Counter(arr)\n",
    "        ls=sorted(list(c.keys()),key=lambda x:abs(x))\n",
    "        for i in ls:\n",
    "            if c[i*2]<c[i]:\n",
    "                return False\n",
    "            c[i*2]-=c[i]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "        c = Counter(arr)\n",
    "        l = list(c)\n",
    "        l.sort(key = lambda x: abs(x))\n",
    "\n",
    "        for i in l:\n",
    "            if c[2*i] < c[i]:\n",
    "                return False\n",
    "            else:\n",
    "                c[2*i] -= c[i]\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        #arr.sort()\n",
    "        arr_a = []\n",
    "        arr_b = []\n",
    "        for item in arr:\n",
    "            if item >= 0:\n",
    "                arr_a.append(item)\n",
    "            else:\n",
    "                arr_b.append(item)\n",
    "        arr_a.sort()\n",
    "        arr_b.sort(reverse=True)\n",
    "        print(arr_a)\n",
    "        print(arr_b)\n",
    "        print(len(arr))\n",
    "        counter = 0\n",
    "        left = {}\n",
    "        over = []\n",
    "        for item in list(set(arr_a)):\n",
    "            double = 2 * item\n",
    "            if item in over:\n",
    "                continue\n",
    "            if item == double:\n",
    "                counter += arr.count(item) // 2\n",
    "                continue\n",
    "            if double in arr:\n",
    "                if item in left:\n",
    "                    a = left[item]\n",
    "                else:\n",
    "                    a = arr.count(item)\n",
    "                b = arr.count(double)\n",
    "                if a >= b:\n",
    "                    counter += b\n",
    "                    over.append(double)\n",
    "                else:\n",
    "                    counter += a\n",
    "                    left[double] = b - a\n",
    "        print(counter)\n",
    "        temp = list(set(arr_b))\n",
    "        temp.sort(reverse=True)\n",
    "        for item in temp:\n",
    "            double = 2 * item\n",
    "            if item in over:\n",
    "                continue\n",
    "            if item == double:\n",
    "                counter += arr.count(item) // 2\n",
    "                continue\n",
    "            if double in arr:\n",
    "                if item in left:\n",
    "                    a = left[item]\n",
    "                else:\n",
    "                    a = arr.count(item)\n",
    "                b = arr.count(double)\n",
    "                if a >= b:\n",
    "                    counter += b\n",
    "                    over.append(double)\n",
    "                else:\n",
    "                    counter += a\n",
    "                    left[double] = b - a\n",
    "            #print(item, counter)\n",
    "        if counter == len(arr) // 2:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        z = [i for i in arr if i>=0]\n",
    "        f = [-i for i in arr if i<0]\n",
    "        \n",
    "        z.sort()\n",
    "        f.sort()\n",
    "        zz = []\n",
    "        if z:\n",
    "            cur = z[0]\n",
    "            count = 1\n",
    "            for i in range(1,len(z)):\n",
    "                if z[i]!=cur:\n",
    "                    zz.append([cur,count])\n",
    "                    cur = z[i]\n",
    "                    count=1\n",
    "                else:\n",
    "                    count+=1\n",
    "            zz.append([cur,count])\n",
    "            if zz[0][0] == 0:\n",
    "                if zz[0][1]%2==0:\n",
    "                    zz.pop(0)\n",
    "                else:\n",
    "                    return False\n",
    "        ff = []\n",
    "        if f:\n",
    "            cur = f[0]\n",
    "            count = 1\n",
    "            for i in range(1,len(f)):\n",
    "                if f[i]!=cur:\n",
    "                    ff.append([cur,count])\n",
    "                    cur = f[i]\n",
    "                    count=1\n",
    "                else:\n",
    "                    count+=1\n",
    "            ff.append([cur,count])\n",
    "        print(zz)\n",
    "        print(ff)\n",
    "        zzdict = {}\n",
    "        for i in range(len(zz)):\n",
    "            zzdict[zz[i][0]] = zz[i][1]\n",
    "        for i in range(len(zz)):\n",
    "            if zzdict[zz[i][0]]>0:\n",
    "                if zz[i][0]*2 in zzdict.keys() and zzdict[zz[i][0]]<=zzdict[zz[i][0]*2]:\n",
    "                    zzdict[zz[i][0]*2]-=zzdict[zz[i][0]]\n",
    "                else:\n",
    "                    print(zz[i])\n",
    "                    print(zzdict)\n",
    "                    print(1)\n",
    "                    return False\n",
    "        ffdict = {}\n",
    "        for i in range(len(ff)):\n",
    "            ffdict[ff[i][0]] = ff[i][1]\n",
    "        for i in range(len(ff)):\n",
    "            if ffdict[ff[i][0]]>0:\n",
    "                if ff[i][0]*2 in ffdict.keys() and ffdict[ff[i][0]]<=ffdict[ff[i][0]*2]:\n",
    "                    ffdict[ff[i][0]*2]-=ffdict[ff[i][0]]\n",
    "                else:\n",
    "                    # print(ff[i])\n",
    "                    # print(2)\n",
    "                    return False \n",
    "        return True           \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "        cnt  = Counter(arr)\n",
    "        keys = list(cnt.keys())\n",
    "        keys.sort()\n",
    "        for k in keys:\n",
    "            if k not in cnt:\n",
    "                continue\n",
    "            if k==0:\n",
    "                if cnt[k]%2==1:\n",
    "                    return False\n",
    "                cnt.pop(0)\n",
    "                continue\n",
    "            if k<0:\n",
    "                if k%2==1:\n",
    "                    return False\n",
    "                if k//2 in cnt:\n",
    "                    t = min(cnt[k],cnt[k//2])\n",
    "                    cnt[k]-=t\n",
    "                    cnt[k//2]-=t\n",
    "                    if cnt[k]==0:\n",
    "                        cnt.pop(k)\n",
    "                    if cnt[k//2]==0:\n",
    "                        cnt.pop(k//2)\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if k*2 in cnt:\n",
    "                    t = min(cnt[k],cnt[k*2])\n",
    "                    cnt[k]-=t\n",
    "                    cnt[k*2]-=t\n",
    "                    if cnt[k]==0:\n",
    "                        cnt.pop(k)\n",
    "                    if cnt[k*2]==0:\n",
    "                        cnt.pop(k*2)\n",
    "                else:\n",
    "                    return False\n",
    "        return True if len(cnt)==0 else False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\r\n",
    "        cnt = Counter(arr)\r\n",
    "        if cnt[0] & 1:\r\n",
    "            return False\r\n",
    "        for x in sorted(cnt, key=abs):\r\n",
    "            if cnt[x] > cnt[2 * x]:\r\n",
    "                return False\r\n",
    "            cnt[2 * x] -= cnt[x]\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        num_map = collections.Counter(arr)\n",
    "        for num in sorted(num_map, key=abs):\n",
    "            print(num)\n",
    "            if num_map[num] > num_map[2 * num]:\n",
    "                return False\n",
    "            num_map[2 * num] -= num_map[num]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        arr.sort(key = lambda x:abs(x))\n",
    "        numDict = collections.defaultdict(int)\n",
    "        cnt = 0\n",
    "        for num in arr:\n",
    "            if num % 2 == 0 and numDict[num // 2] > 0:\n",
    "                numDict[num // 2] -= 1\n",
    "                if numDict[num // 2] == 0:  cnt -= 1\n",
    "            else:\n",
    "                if numDict[num] == 0:   cnt += 1\n",
    "                numDict[num] += 1\n",
    "        return cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        a = [0 for _ in range(100001)]\n",
    "        b = [0 for _ in range(100001)]\n",
    "\n",
    "        for v in arr:\n",
    "            if v >= 0:\n",
    "                a[v] += 1\n",
    "            else:\n",
    "                b[-v] += 1\n",
    "        \n",
    "        for i in range(100001):\n",
    "            if a[i]:\n",
    "\n",
    "                if 2*i > len(a) or a[2*i] < a[i]:\n",
    "                    return False\n",
    "                a[2*i] -= a[i]\n",
    "\n",
    "            if b[i]:\n",
    "                if (b[i] and 2*i > len(b)) or b[2*i] < b[i]:\n",
    "                    return False\n",
    "                b[2*i] -= b[i]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        count1 = [0]*100001\n",
    "        count2 = [0]*100001\n",
    "        max1 = -200000\n",
    "        max2 = -200000\n",
    "        for i in arr:\n",
    "            if i >= 0:\n",
    "                count1[i] += 1\n",
    "                max1 = max(max1,i)\n",
    "            else:\n",
    "                count2[-i] += 1\n",
    "                max2 = max(max2,-i)\n",
    "            \n",
    "        for i in range(max1+1):\n",
    "            if count1[i] != 0:\n",
    "                try:\n",
    "                    tmp = count1[2 * i]\n",
    "                except:\n",
    "                    return False\n",
    "                count1[2 * i] -= count1[i]\n",
    "                count1[i] = 0\n",
    "                if count1[2 * i] < 0:\n",
    "                    return False\n",
    "        for i in range(max2+1):\n",
    "            if count2[i] != 0:\n",
    "                try:\n",
    "                    tmp = count2[2 * i]\n",
    "                except:\n",
    "                    return False\n",
    "                count2[2 * i] -= count2[i]\n",
    "                count2[i] = 0\n",
    "                if count2[2 * i] < 0:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        # [4,-2,2,-4]\n",
    "        arr.sort(key=lambda x: abs(x))\n",
    "\n",
    "        cnter = Counter(arr)\n",
    "        for i in range(len(arr)):\n",
    "            x = arr[i]\n",
    "            if cnter[x] > 0:\n",
    "                cnter[x] -= 1\n",
    "                cnter[2*x] -= 1\n",
    "                if cnter[2*x] < 0:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "        cnt = Counter(arr)\n",
    "        arr = list(set(arr))\n",
    "        arr.sort()\n",
    "        if 0 in cnt:\n",
    "            if cnt[0] % 2: return False\n",
    "        del cnt[0]\n",
    "        for x in arr:\n",
    "            if cnt[x]:\n",
    "                s = cnt[x * 2] if x * 2 != x else 0\n",
    "                s += cnt[x // 2] if x // 2 != x and x // 2 * 2 == x else 0\n",
    "                if s >= cnt[x]:\n",
    "                    if x // 2 != x and cnt[x // 2] != 0:\n",
    "                        if cnt[x] >= cnt[x // 2]:\n",
    "                            cnt[x] -= cnt[x // 2]\n",
    "                            cnt[x // 2] = 0\n",
    "                        else:\n",
    "                            cnt[x // 2] -= cnt[x]\n",
    "                            cnt[x] = 0\n",
    "                    if cnt[x]:\n",
    "                        cnt[x * 2] -= cnt[x]\n",
    "                        cnt[x] = 0\n",
    "                else:\n",
    "                    return False\n",
    "        for k in cnt:\n",
    "            if cnt[k] > 0: return False\n",
    "        return True\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        count1 = [0]*100001\n",
    "        count2 = [0]*100001\n",
    "        max1 = -200000\n",
    "        max2 = -200000\n",
    "        for i in arr:\n",
    "            if i >= 0:\n",
    "                count1[i] += 1\n",
    "                max1 = max(max1,i)\n",
    "            else:\n",
    "                count2[-i] += 1\n",
    "                max2 = max(max2,-i)\n",
    "        max3 = max(max1,max2)\n",
    "        for i in range(max3+1):\n",
    "            if count1[i] != 0:\n",
    "                try:\n",
    "                    tmp = count1[2 * i]\n",
    "                except:\n",
    "                    return False\n",
    "                count1[2 * i] -= count1[i]\n",
    "                count1[i] = 0\n",
    "                if count1[2 * i] < 0:\n",
    "                    return False\n",
    "            if count2[i] != 0:\n",
    "                try:\n",
    "                    tmp = count2[2 * i]\n",
    "                except:\n",
    "                    return False\n",
    "                count2[2 * i] -= count2[i]\n",
    "                count2[i] = 0\n",
    "                if count2[2 * i] < 0:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        cnt0, ps, ns = 0, [], []\n",
    "        for val in arr:\n",
    "            if val == 0: cnt0 += 1\n",
    "            elif val > 0: ps.append(val) \n",
    "            else: ns.append(val)\n",
    "        if cnt0 % 2 == 1: return False\n",
    "        ps.sort()\n",
    "        cnts = collections.Counter(ps)\n",
    "        for v in ps:\n",
    "            if cnts[v] > 0:\n",
    "                if cnts[2 * v] > 0:\n",
    "                    cnts[v] -= 1\n",
    "                    cnts[2 * v] -= 1\n",
    "                else:\n",
    "                    return False\n",
    "        ns.sort(reverse = True)\n",
    "        cnts = collections.Counter(ns)\n",
    "        for v in ns:\n",
    "            if cnts[v] > 0:\n",
    "                if cnts[2 * v] > 0:\n",
    "                    cnts[v] -= 1\n",
    "                    cnts[2 * v] -= 1\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        n = len(arr)\n",
    "        rec_dict = collections.defaultdict(int)\n",
    "        for v in arr:\n",
    "            rec_dict[v] += 1\n",
    "        arr.sort(key=abs)\n",
    "        cnt = 0\n",
    "        for v in arr:\n",
    "            # print(v)\n",
    "            # print(rec_dict)\n",
    "            if rec_dict[v] == 0:\n",
    "                continue\n",
    "            rec_dict[v] -= 1\n",
    "            if rec_dict[2*v] != 0:\n",
    "                rec_dict[2*v] -= 1\n",
    "            else:\n",
    "                return False\n",
    "            cnt += 1\n",
    "            if cnt == n //2:\n",
    "                break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        pos = {}\n",
    "        neg = {}\n",
    "        arr1 = []\n",
    "        arr2 = []\n",
    "        arr0 = []\n",
    "        for num in arr:\n",
    "            if num < 0:\n",
    "                arr2.append(-num)\n",
    "            elif num > 0:\n",
    "                arr1.append(num)\n",
    "            else:\n",
    "                arr0.append(num)\n",
    "        if len(arr0) % 2 != 0 or len(arr1) % 2 != 0 or len(arr2) % 2 != 0:\n",
    "            return False\n",
    "        arr1.sort()\n",
    "        arr2.sort()\n",
    "        record_pos = {}\n",
    "        record_neg = {}\n",
    "        for i in arr1:\n",
    "            if i not in pos:\n",
    "                pos[i] = 1\n",
    "            else:\n",
    "                pos[i] += 1\n",
    "        for i in arr2:\n",
    "            if i not in neg:\n",
    "                neg[i] = 1\n",
    "            else:\n",
    "                neg[i] += 1\n",
    "        for i in arr1:\n",
    "            if i not in record_pos:\n",
    "                if 2 * i not in pos:\n",
    "                    return False\n",
    "                record_pos[i] = 1\n",
    "                record_pos[2 * i] = 1\n",
    "            elif record_pos[i] < pos[i]:\n",
    "                if (2 * i not in pos) or (2 * i in record_pos and record_pos[2 * i] >= pos[2 * i]):\n",
    "                    return False\n",
    "                record_pos[i] += 1\n",
    "                if 2 * i not in record_pos:\n",
    "                    record_pos[2 * i] = 1\n",
    "                else:\n",
    "                    record_pos[2 * i] += 1\n",
    "        for i in arr2:\n",
    "            if i not in record_neg:\n",
    "                if 2 * i not in neg:\n",
    "                    return False\n",
    "                record_neg[i] = 1\n",
    "                record_neg[2 * i] = 1\n",
    "            elif record_neg[i] < neg[i]:\n",
    "                if (2 * i not in neg) or (2 * i in record_neg and record_neg[2 * i] >= neg[2 * i]):\n",
    "                    return False\n",
    "                record_neg[i] += 1\n",
    "                if 2 * i not in record_neg:\n",
    "                    record_neg[2 * i] = 1\n",
    "                else:\n",
    "                    record_neg[2 * i] += 1\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        import collections\n",
    "        count = collections.Counter(arr)\n",
    "        for x in sorted(arr, key = abs):\n",
    "            if count[x] == 0: continue\n",
    "            if count[2*x] == 0: return False\n",
    "            count[x] -= 1\n",
    "            count[2*x] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr) -> bool:\n",
    "        ans=[]#正\n",
    "        array=[]#负\n",
    "        h=[]#0\n",
    "        for i in arr:\n",
    "            if i==0:\n",
    "                h.append(i)\n",
    "            if i>0:\n",
    "                ans.append(i)\n",
    "            if i<0:\n",
    "                array.append(i)\n",
    "        ans.sort()\n",
    "        array.sort(reverse=True)\n",
    "        ans=array+ans\n",
    "        if len(h)%2==1:\n",
    "            return False\n",
    "        d={}\n",
    "        for i in ans:\n",
    "           d[i]=d.get(i,0)+1\n",
    "        for i in d:\n",
    "            if i*2 in d:\n",
    "                t=min(d[i],d[i*2])\n",
    "                d[i*2]-=t\n",
    "                d[i] -= t\n",
    "            if     d[i]!=0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        pair = 0\n",
    "        n = len(arr)\n",
    "        numDict = collections.defaultdict(int)\n",
    "        arr.sort(key=lambda x:abs(x))\n",
    "        for num in arr:\n",
    "            if num % 2 == 0 and numDict[num // 2] > 0:\n",
    "                numDict[num // 2] -= 1\n",
    "                pair += 1\n",
    "            else:\n",
    "                numDict[num] += 1\n",
    "        \n",
    "        return pair == n // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        if len(arr) % 2:\n",
    "            return False\n",
    "        res = [0] * (200000 + 1)\n",
    "        for num in arr:\n",
    "            res[num+100000] += 1\n",
    "        for i in range(200000, 100000, -1):\n",
    "            num = i - 100000\n",
    "            if num % 2 and res[i] > 0:\n",
    "                return False\n",
    "            if res[i] > 0:\n",
    "                res[num//2 + 100000] -= res[i]\n",
    "                res[i] = 0\n",
    "                if res[num//2 + 100000] < 0:\n",
    "                    return False\n",
    "        if res[100000] % 2:\n",
    "            return False\n",
    "        for j in range(0, 100000):\n",
    "            num = j - 100000\n",
    "            if num % 2 and res[j] > 0:\n",
    "                return False\n",
    "            if res[j] > 0:\n",
    "                res[num//2 + 100000] -= res[j]\n",
    "                res[j] = 0\n",
    "                if res[num//2 + 100000] < 0:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReorderDoubled(self, arr: List[int]) -> bool:\n",
    "        from sortedcontainers import SortedDict\n",
    "        def check(arr, sign):\n",
    "            cnt = SortedDict()\n",
    "            for x in arr:\n",
    "                if x * sign > 0:\n",
    "                    cnt[x * sign] = cnt.get(x * sign, 0) + 1\n",
    "            \n",
    "            while len(cnt):\n",
    "                x = cnt.keys()[0]\n",
    "                if cnt[x] == 0:\n",
    "                    del cnt[x]\n",
    "                else:\n",
    "                    if cnt.get(2 * x, 0) == 0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        cnt[2 * x] -= 1\n",
    "                        cnt[x] -= 1\n",
    "            return True\n",
    "        \n",
    "        return check(arr, 1) and check(arr, -1)\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
